
\chapter{Dobrá předuspořádání a regularita}
Na konci první kapitoly jsme se zamysleli nad možností rozpoznávat regulární jazyky předuspořádáními nekonečných indexů. Jak bylo uvedeno, odpovědí jsou dobrá předuspořádání představená v minulé kapitole. Myhillova-Nerodova věta se na jejich základě dá zoběcnit do následujícího tvaru.


\begin{veta}
\label{genMyh}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
monotónnímu dobrému předuspořánaní množiny $\Sigma^*$.
\end{veta}

\begin{proof}


V první řadě platí, že každé předuspořádání konečného indexu je dobré. Stačí nám tedy ukázat, že podmnožiny množiny $\Sigma^*$ uzavřené
vzhledem k monotónnímu dobrému předuspořádání jsou regulární. Důkaz provedeme sporem. Předpokládejme tedy, že máme monotónní dobré předuspořádání $\leq$ na množině
$\Sigma^*$ a množinu $L$ uzavřenou vzhledem k $\leq$, která není regulární. Z věty \ref{Myhill-Nerode} plyne, že relace $\sim_L$ má nekonečný index,
můžeme proto sestrojit nekonečnou posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle definice \ref{wqo} můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$
vybrat rostoucí podposloupnost vzhledem k $\leq$. Můžeme tedy předpokládat, že už samotná posloupnost $\{x_i\}_{i=1}^\infty$ byla vybrána jako rostoucí.
Z monotónie dostáváme, že pro libovolné $y \in \Sigma^*$ a $i < j $ platí $x_i y \leq x_j y$ a z uzavřenosti množiny $X$ plyne, že 
$x_i y \in L \Longrightarrow x_j y \in L $. Proto platí, že posloupnost pravých kontextů $\{C_L^r(x_i)\}_{i=1}^\infty$ je rostoucí vzhledem k inkluzi, a to dokonce ostře, 
neboť slova $x_i$ nejsou vzájemně ekvivalentní. Dále pro libovoná slova $y_1, y_2 \in \Sigma^*$ taková, že $y_1 \leq y_2$, platí $x_i y_1 \in L \Longrightarrow x_i y_2 \in L $.
Jsou tedy množiny $C_L^r(x_i)$  rovněž uzavřené vzhledem k  $\leq$. Posloupnost $\{C_L^r(x_i)\}_{i=1}^\infty$ je tedy nekonečná posloupnost uzavřených množin
ostře rostoucí vzhledem k inkluzi. Dostáváme spor, neboť podle definice \ref{wqo} části (vi) takováto posloupnost není možná. Množina $L$ 
tedy musí být regulární.
 \end{proof}

V předchozím tvrzení jsme dostali zobecnění Nerodovy věty tím, že místo pravé kongruence jsme použili monotónní předuspořádání. V důkazu jsme využili monónnost z prava i zleva,
v případě kongruence nám však stačila pouze monotonie zprava. Jak se ukáže na příkladu na konci kapitoly, uzavřenost vzhledem k jednostranně monotónnímu dobrému předuspořádání k regularitě vést nemusí. Věta \ref{genMyh} se přesto dá zobecnit. Stačí nalézt dvě dobrá předuspořádání $\leq_1 , \leq_2$, vzhledem k nimž bude jazyk $L$ uzavřený, přičemž $\leq_1$ je monotónní zprava
a $\leq_2$ zleva. 

\begin{veta}
\label{genMyh2}
Nechť $L\subseteq\Sigma^*$.  Potom $L$ je regulární právě tehdy, když je uzavřený vzhledem k nějakému 
 dobrému předuspořánaní  $\leq_1$ monotónnímu zprava a  dobrému předuspořánaní  $\leq_2$ monotónnímu zleva.

\end{veta}

K důkazu věty budeme potřebovat několik pojmů. Podobně jako jsme v definici \ref{kontext} definovali na základě kontextu syntaktickou kongruenci, si zadefinujeme \emph{syntaktické monotónní předuspořádání}.

\begin{definice}
Pro $L \subseteq\Sigma^* $ a prvky $x,y \in \Sigma^*$ definujeme relace:
  \[x\leq_L y  \Longleftrightarrow C_L(x) \subseteq C_L(y).\]
  \[x\leq_L^r y  \Longleftrightarrow C_L^r(x) \subseteq C_L^r(y).\]
  \[x\leq_L^l y  \Longleftrightarrow C_L^l(x) \subseteq C_L^l(y).\]
\end{definice}
Podobně jako v případě syntaktické kongruence se snadno ukáže, že syntaktické monotónní předuspořádání (resp. pravé/lévé) je největší monotónní předuspořádání, vzhledem k němuž je jazyk $L$ uzavřený.

\begin{lemma}
\label{monwqo}
 Nechť $L\subseteq\Sigma^*$ a $\leq$ je libovolné pravé (resp. levé) monotónní  předuspořádání na $\Sigma^*$, vzhledem ke kterému je jazyk $L$ uzavřený.  Potom platí, že $\leq \;\subseteq\; \leq_L^r$ (resp. $\leq \;\subseteq\; \leq_L^l$ ). 
\end{lemma}



\begin{proof}
Budeme dokazovat případ pro pravé monotńní předuspořádání.
Nechť  $x, y \in \Sigma^*$ jsou libovolná slova taková, že platí $x \leq y$. Z monotónnie $\leq$ plyne, že $xz \leq yz$ pro libovolné $z \in \Sigma^*$. 
Z uzavřenosti jazyka $L$ vzhledem k $\leq$ potom vyplývá, že $xz \in L \Longrightarrow yz \in L$ a tedy $ C_L^r(x) \subseteq C_L^r(y)$.

\end{proof}

Poslední vlastnost, kterou v důkazu věty \ref{genMyh2} využijeme, je, že se stačí zaměřit právě na předuspořádání $\leq_L^r$ a $\leq_L^l$. Najdeme-li totiž nějaká předuspořádání $\leq_1 , \leq_2$, která splňují podmínky věty \ref{genMyh2}, pak mají tuto vlastnost i $\leq_L^r$, $\leq_L^l$.

\begin{lemma}
\label{subwqo}
Nechť  $\leq_1$ je dobré předuspořádání a  $\leq_2$ je předuspořádání takové, že platí   $\leq_1\subseteq  \leq_2$. Potom je předuspořádání $\leq_2$ dobré.
\end{lemma}
\begin{proof}
K důkazu využijeme definici \ref{wqo}(ii). Pro  $\leq_1$ platí, že v libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že $x_i \leq_1 x_j$, tedy i   $x_i \leq_2 x_j$. Předuspořádání  $\leq_2$ je proto také dobré.
\end{proof}

\begin{proof}[Důkaz věty \ref{genMyh2}]
Je-li jazyk $L$ regulární, pak podle věty \ref{genMyh} víme, že je uzavřený vzhledem k dobrému předuspořádání, které je monotónní zprava i zleva. Opačnou implikaci budeme dokazovat sporem.
Nechť tedy $L$ není regulární. Potom podle věty \ref{Myhill-Nerode} má relace $\sim_L^r$ nekonečný index a existuje proto nekonečná posloupnost vzájemně neekvivalentních slov $\{x_i\}_{i=1}^\infty$. Podle předpokladu existují dobrá předuspořádání 
$\leq_1$ resp. $\leq_2$ monotónní zprava resp. zleva, vzhledem k nimž je $L$ uzavřený. Podle lemmat \ref{monwqo} a \ref{subwqo} mají tuto vlastnost také předuspořádání $\leq_L^r$, $\leq_L^l$. Z definice \ref{wqo}(ii) můžeme z posloupnosti $\{x_i\}_{i=1}^\infty$ vybrat podposloupnost $\{y_i\}_{i=1}^\infty$, která bude rostoucí vzhledem k předuspořádání $\leq_L^r$ a to dokonce ostře, neboť jsou $y_i$ vzájemně neekvivalentní v relaci $\sim_L^r$. Platí tedy, že 
$C_L^r(y_i) \subset C_L^r(y_{i+1})$ a posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je tedy ostře rostoucí vzhledem k inkluzi. Je zřejmé, že platí vztah $x\in C_L^r(y) \Longleftrightarrow y\in C_L^l(x) $. Z toho pro libovolná $z_1 \leq_L^l z_2$ plyne, že $z_1 \in C_L^r(y_i) \Longrightarrow y_i \in C_L^l(z_1) \subseteq C_L^l(z_2) \Longrightarrow z_2\in C_L^r(y_i)$.  Posloupnost $\{C_L^r(y_i)\}_{i=1}^\infty$ je pak posloupností uzavřených množin vzhledem k předuspořádání  $\leq_L^l$, která je ostře rostoucí vzhledem k inkluzi. To je ovšem spor s předpokladem, že předuspořádání  $\leq_L^l$ je dobré.
\end{proof}

Následuje slíbený příklad, na kterém si demonstrujeme, že jednostranná monotonie v případě předuspořádání nezaručuje regularitu.

\begin{priklad}
Mějmě jazyk $L=\{a^nb^m | 0\leq n\leq m\}$. Ukážeme, že pravé syntaktické předuspořádání $\leq^r_L$ je dobré a přítom jazyk $L$ není regulární.

Nejdříve ukážeme, jak vypadají pravé kontexty. Slova si rozdělíme do čtyř skupin podle jejich tvaru a odpovídajícího pravého kontextu. První skupina slov má tvar $x \in \{a, b\}^*\cdot ba \cdot \{a, b\}^*$, tato slova zřejmě nejsou prvky jazyka $L$ a přidáním libovolného suffixu se to nezmění. Jejich pravý kontext je proto $C^r_L(x)=\O $. Další skupina slov má tvar $x= a^nb^m$, kde $1\leq m<n$. Tato slova také nepatří do $L$, ale přídáním dostatečného počku $b$ na konec již budou mít požadovaný tvar. Jejich pravý kontext je $C^r_L(a^nb^m)=\{b^k| k\geq n-m\} $. Předposlední skupinou slov jsou ta tvaru $x= a^n$, kde $0\leq n$, která mají kontext $C^r_L(a^n)=\{a^kb^l| l\geq n+k\} $. Konečně pro slova tvaru $x= a^nb^m$, kde $ 0\leq n\leq m,1\leq m$ platí $C^r_L(x)=\{b^k| k\geq 0\} $.

\vskip 0.25cm
\begin{tabular}{l|l}

  $\{a, b\}^*\cdot ba \cdot \{a, b\}^*$   	& 	$\O $ \\
  $a^n$\hskip 0.46cm , kde $0 \leq n$   				& 	$\{a^kb^l| l\geq n+k\} $\\
  $a^nb^m$, kde $ 1\le m \le n$       		& 	$\{b^k| k\geq n-m\} $ \\

  $a^nb^m$, kde $ 0\leq n\leq m, 1 \leq m$  	& 	$\{b^k| k\geq 0\} $ \\
\end{tabular}
\vskip 0.25cm 
\noindent 
Abychom dokázali, že je toto předuspořádání dobré, stačí si uvědomit, že slova ze stejné skupiny (stejný řádek v tabulce) jsou vždy porovnatelná. Pro libovolnou podmnožinu $X \subseteq \{a, b\}^*$ tedy existuje konečná podmnožina $Y\subseteq X$, která obsahuje jeden minimální prvek pro každou skupinu slov, která je v $X$ zastoupena.

Dále si ukážeme, že jazyk $L$ je uzavřený na předuspořádání $\leq^r_L$. Platí, že každý jazyk je uzavřený vzhledem ke svému pravému syntaktickému předuspořádání. Pro představu si to však dokážeme pro konkrétní případ. Musíme ověřit, že platí vztah
\[\forall x\in \{a, b\}^*\;\forall w \in L : w\leq^r_L x \Longrightarrow x\in L\]
Z tabulky je patrné, že neprázdná slova jazyka $L$ mají shodný pravý kontext $C^r_L(x)=\{b^k| k\geq 0\} $, který není podmnožinou kontextu žádného slova, které do $L$ nepatří. Pravý kontext prázdného slova je množina $L$ a pravý kontext žádného jiného slova ji neobsahuje jako podmnožinu. Jazyk $L$ je tedy uzavřený na monotónní dobré předuspořádání $\leq^r_L$.

Jazyk $L$ však není regulární, což lze jednoduše ukázat například sestrojením minimálního automatu. Každý automat přijímající jazyk $L$ si totiž musí při čtení vstupu nejprve pamatovat počet výskytů písmene $a$, kterých však může být libovolně mnoho.
\end{priklad}
\cleardoublepage

